public class MergeSortTest {
    /**
     * 归并排序
     * 利用二分和递归，将数组元素排序进行排序后进行合并
     * 最优的时间复杂度为O（nlogn）（n为比较的元素个数）
     */
    public static void merge(int[] arr,int left,int mid,int right){
        int n1=mid-left+1;
        int n2=right-mid;

        // 创建新的数组并进行复制
        int[] L = new int[n1];
        int[] R = new int[n2];
        for (int i = 0; i < n1; ++i)
            L[i] = arr[left + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[mid + 1 + j];

        // 比较两个数组
        int i=0,j=0;
        int k=left;
        while(i<n1 && j<n2){
            if(L[i]<=R[j]){
                arr[k]=L[i];
                i++;
            }else {
                arr[k]=R[j];
                j++;
            }
            k++;
        }

        // 将剩余的元素复制进去
        while (i<n1){
            arr[k]=L[i];
            i++;
            k++;
        }

        while (j<n2){
            arr[k]=R[j];
            j++;
            k++;
        }

    }

    public static void mergeSort(int[] arr,int left,int right){
        if(left<right){
            int mid=left+(right-left)/2;

            // 分割数组并进行递归的操作
            mergeSort(arr, left, mid);
            mergeSort(arr, mid+1, right);

            // 进行合并两个子数组的操作
            merge(arr,left,mid,right);
        }
    }

    public static void main(String[] args) {
        int[] arr = {5, 2, 9, 1, 6, 3};

        mergeSort(arr, 0, arr.length - 1);

        // 输出排序结果
        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}
